package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 1584. 连接所有点的最小费用
 * 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
 *
 * 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
 *
 * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
 * 输出：20
 * 解释：
 *
 * 我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
 * 注意到任意两个点之间只有唯一一条路径互相到达。
 * 示例 2：
 *
 * 输入：points = [[3,12],[-2,5],[-4,1]]
 * 输出：18
 * 示例 3：
 *
 * 输入：points = [[0,0],[1,1],[1,0],[-1,1]]
 * 输出：4
 * 示例 4：
 *
 * 输入：points = [[-1000000,-1000000],[1000000,1000000]]
 * 输出：4000000
 * 示例 5：
 *
 * 输入：points = [[0,0]]
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= points.length <= 1000
 * -106 <= xi, yi <= 106
 * 所有点 (xi, yi) 两两不同。
 * @author SHM
 */
public class MinCostConnectPoints {
    /**
     * 写在前面
     * 根据题意，我们得到了一张 nn 个节点的完全图，任意两点之间的距离均为它们的曼哈顿距离。现在我们需要在这个图中取得一个子图，恰满足子图的任意两点之间有且仅有一条简单路径，且这个子图的所有边的总权值之和尽可能小。
     *
     * 能够满足任意两点之间有且仅有一条简单路径只有树，且这棵树包含 nn 个节点。我们称这棵树为给定的图的生成树，其中总权值最小的生成树，我们称其为最小生成树。
     *
     * 最小生成树有一个非常经典的解法：\text{Kruskal}Kruskal。
     *
     * 方法一：\text{Kruskal}Kruskal 算法
     * 思路及解法
     *
     * \text{Kruskal}Kruskal 算法是一种常见并且好写的最小生成树算法，由 \text{Kruskal}Kruskal 发明。该算法的基本思想是从小到大加入边，是一个贪心算法。
     *
     * 其算法流程为：
     *
     * 将图 G=\{V,E\}G={V,E} 中的所有边按照长度由小到大进行排序，等长的边可以按任意顺序。
     *
     * 初始化图 G'G
     * ′
     *   为 \{V,\varnothing\}{V,∅}，从前向后扫描排序后的边，如果扫描到的边 ee 在 G'G
     * ′
     *   中连接了两个相异的连通块,则将它插入 G'G
     * ′
     *   中。
     *
     * 最后得到的图 G'G
     * ′
     *   就是图 GG 的最小生成树。
     *
     * 在实际代码中，我们首先将这张完全图中的边全部提取到边集数组中，然后对所有边进行排序，从小到大进行枚举，每次贪心选边加入答案。使用并查集维护连通性，若当前边两端不连通即可选择这条边。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n^2\log(n))O(n
     * 2
     *  log(n))，其中 nn 是节点数。一般 \text{Kruskal}Kruskal 是 O(m\log m)O(mlogm) 的算法，但本题中 m=n^2m=n
     * 2
     *  ，因此总时间复杂度为 O(n^2\log(n))O(n
     * 2
     *  log(n))。
     *
     * 空间复杂度：O(n^2)O(n
     * 2
     *  )，其中 nn 是节点数。并查集使用 O(n)O(n) 的空间，边集数组需要使用 O(n^2)O(n
     * 2
     *  ) 的空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points/solution/lian-jie-suo-you-dian-de-zui-xiao-fei-yo-kcx7/
     * @param points
     * @return
     */
    public int minCostConnectPoints(int[][] points) {
        int len = points.length;
        UnionFind uf = new UnionFind(len);
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                edges.add(new Edge(dis(points,i,j),i,j));
            }
        }

        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.len-o2.len;
            }
        });

        int ret=0,num=1;
        for (Edge edge : edges) {
            int l = edge.len;
            if(uf.union(edge.x,edge.y)){
                ret+=l;
                num++;
                if(num==len){
                    break;
                }
            }
        }
        return ret;
    }

    int dis(int[][] points,int x,int y){
        return Math.abs(points[x][0]-points[y][0])+Math.abs(points[x][1]-points[y][1]);
    }
    class UnionFind{
        int[] parent;
        int[] rank;

        UnionFind(int n){
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        int find(int x){
            if(parent[x]!=x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int x,int y){
            int newX = find(x);
            int newY = find(y);
            if(newX==newY){
                return false;
            }
            if(rank[newX]<rank[newY]){
                int temp = rank[newX];
                rank[newX] = rank[newY];
                rank[newY] = temp;
            }
            parent[newY] = newX;
            rank[newX]+=rank[newY];
            return true;
        }
    }

    class Edge{
        int len,x,y;
        Edge(int len,int x,int y){
            this.len = len;
            this.x = x;
            this.y = y;
        }

    }
}
